#include<stdio.h>
#include<stdlib.h>

#define LEN 8

int a[LEN]	= {5, 2, 4, 7, 1, 3, 2, 6};

void printArrayElement( void );

void
merge(int start, int mid, int end) {
	int n1	= mid - start + 1;
	int n2	= end - mid;
	int * left, * right;
	int i,j,k;
	
	left	= (int *) malloc (n1 * sizeof(int));
	right	= (int *) malloc (n2 * sizeof(int));

	printf("Left:");
	for(i = 0; i < n1; i ++) {
		left[i]		= a[start + i];
		printf("%d ", left[i]);
	}
	printf("\n");
	printf("Right:");
	for(j = 0; j < n2; j ++ ) {
		right[j]	= a[mid + j + 1];
		printf("%d ", right[j]);
	}
	printf("\n");
	i = j = 0;
	for(k = start; i < n1 && j < n2; k ++) {
		if(left[i] < right[j]) {
			a[k]	= left[i];
			i ++;
		} else {
			a[k]	= right[j];
			j ++;
		}
	}
	if(i < n1) {
		for(; i < n1; i ++) {
			a[k]	= left[i];
			k ++;
		}
	} else {
		for(; j < n2; j ++) {
			a[k]	= right[j];
			k ++;
		}
	}
}

void
sort(int start, int end) {
	int mid;
	if(start < end) {
		mid		= (start + end) / 2;
		printf("sort (%d - %d, %d - %d) ", start, mid, mid + 1, end);
		printArrayElement();
		sort(start, mid);
		sort(mid + 1, end);
		merge(start, mid, end);
		printf("merge (%d - %d, %d - %d) ", start, mid, mid + 1, end);
		printArrayElement();
	} else {
		printf("start < mid [%d < %d ]\n", start, end);
	}
}

void 
printArrayElement( void ) {
	int i;
	for(i = 0; i < LEN; i ++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

int
main(int * argc, char * argv[]) {
	sort(0, LEN - 1);

	return 0;
}